home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1997 / MacHack 1997.toast / Hacks / Hacks ’97 / Warrior’s Progress / source code / Source / Libraries / Trees / RedBlackKeyTree.h < prev    next >
Encoding:
Text File  |  1997-06-28  |  1.8 KB  |  62 lines  |  [TEXT/CWIE]
  1. // RedBlackKeyTree.h
  2.  
  3. #ifndef RedBlackKeyTree_h
  4. #define RedBlackKeyTree_h
  5.  
  6. #ifndef RedBlackTree_h
  7. #include "RedBlackTree.h"
  8. #endif
  9.  
  10. template < class KeyType > class RedBlackKey;
  11.  
  12. template < class Key >
  13. class RedBlackKeyTree: private RedBlackTree
  14.   {
  15.     friend class RedBlackKey< Key >;
  16.     
  17.     typedef RedBlackKey< Key > Node;
  18.     typedef RedBlackNode NodeBase;
  19.     typedef RedBlackTree TreeBase;
  20.     
  21.     private:
  22.         static Node *DownCast( NodeBase *n );
  23.         static const Node *DownCast( const NodeBase *n );
  24.         
  25.         Node *FindTopmost( const Key& k ) const;
  26.         Node *FindFirst( const Key& k ) const;
  27.         Node *FindLast( const Key& k ) const;
  28.         Node& Lookup( const Key& ) const;    // Throws ElementNotFound if it's not found
  29.         
  30.     public:
  31.         void Add( Node& );
  32.         void Remove( Node& node )        { TreeBase::Remove( node ); }
  33.         
  34.         TreeBase::RemoveAll;
  35.         TreeBase::IsEmpty;
  36.         
  37.         Node *Root()                        { return DownCast( TreeBase::Root() ); }
  38.         const Node *Root() const        { return DownCast( TreeBase::Root() ); }
  39.         
  40.         Node *First()                        { return DownCast( TreeBase::First() ); }
  41.         const Node *First() const        { return DownCast( TreeBase::First() ); }
  42.         
  43.         Node *Last()                        { return DownCast( TreeBase::Last() ); }
  44.         const Node *Last() const        { return DownCast( TreeBase::Last() ); }
  45.         
  46.         Node *First( const Key& k )                    { return FindFirst( k ); }
  47.         const Node *First( const Key& k ) const    { return FindFirst( k ); }
  48.         
  49.         Node *Last( const Key& k )                        { return FindLast( k ); }
  50.         const Node *Last( const Key& k ) const        { return FindLast( k ); }
  51.  
  52.         Node *Find( const Key& k )                        { return FindTopmost( k ); }
  53.         const Node *Find( const Key& k ) const        { return FindTopmost( k ); }
  54.         
  55.         Node& operator[]( const Key& k )                    { return Lookup( k ); }
  56.         const Node& operator[]( const Key& k ) const    { return Lookup( k ); }
  57.         
  58.         bool Valid() const;
  59.   };
  60.  
  61. #endif
  62.